package leetcode101.data_structure;

import javafx.util.Pair;

import java.util.*;

/**
 * @author Synhard
 * @version 1.0
 * @class Code29
 * @description 870. 优势洗牌
 * 给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。
 *
 * 返回 A 的任意排列，使其相对于 B 的优势最大化。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：A = [2,7,11,15], B = [1,10,4,11]
 * 输出：[2,11,7,15]
 * 示例 2：
 *
 * 输入：A = [12,24,8,32], B = [13,25,32,11]
 * 输出：[24,32,8,12]
 *  
 *  
 * 提示：
 *
 * 1 <= A.length = B.length <= 10000
 * 0 <= A[i] <= 10^9
 * 0 <= B[i] <= 10^9
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-05-18 10:05
 */
public class Code29 {

    public static void main(String[] args) {
        int[] nums1 = new int[]{12,24,8,32};
        int[] nums2 = new int[]{13,25,32,11};
        System.out.println(Arrays.toString(advantageCount(nums1, nums2)));
    }

    public static int[] advantageCount(int[] A, int[] B) {
        int[] res = new int[A.length];
        int low, high, mid;
        Arrays.sort(A);
        List<Integer> list4A = new ArrayList<>();
        for (int i : A) {
            list4A.add(i);
        }
        List<Pair<Integer, Integer>> list4B = new ArrayList<>();

        for (int i = 0; i < B.length; i++) {
            list4B.add(new Pair<>(i, B[i]));
        }
        Comparator<Pair<Integer, Integer>> comparator = Comparator.comparing(Pair::getValue);
        list4B.sort(comparator);

        for (Pair<Integer, Integer> pair : list4B) {
            low = -1;
            high = list4A.size();
            while (low + 1 != high) {
                mid = (low + high) >> 1;
                if (list4A.get(mid) <= pair.getValue()) {
                    low = mid;
                } else {
                    high = mid;
                }
            }
            if (high == list4A.size()) { // 没有找到刚好比B大的
                res[pair.getKey()] = list4A.get(0);
                list4A.remove(0);
            } else {
                res[pair.getKey()] = list4A.get(high);
                list4A.remove(high);
            }
        }
        return res;
    }



}

/*
学到了新的数据结构 Pair<K, V>
首先对A数组进行排序
然后构建新的数据结构 List<Pair<Integer, Integer>> 其中 Pair中的 Key 是 B 数组的下标， Value是B数组的值
然后对这个List按照Pair的Value排序即可
然后遍历每一个Pair，使用二分查找查找A中刚好比Pair 的value值大的，找到了就加入结果中，没找到就选一个A中最小的加入
 */